Dual
by
Ross Cutler
5-10-94
rgc@cs.umd.edu

Introduction
Dual is a simple program to illustrate the concept of duality in computational geometry.  The basic idea of duality (as used in this program) is to associate the point (a,b) with the line y=ax-b.  We can do this since a point and a line both require two numbers to be uniquely specified.  For example, the follow 5 points (a-e):

¬

get mapped into the following 5 lines (a-e):

¬

The mapping that we used to transform points to lines is:

L: y=ax-b <=> p:(a,b)

Let D denote this mapping.  The following are properties of D [1]:

P1: D is its own inverse: D(D(x)) = x,  where x is either a point or a line.

P2: D is a 1-1 correspondence between all non-vertical lines and all points in the plane.

P3: Point p lies on line L iff point D(L) lies on line D(p).

P4: Lines L1 and L2 intersect at point p iff the line D(p) passes through the two points D(L1) and D(L2).

P5: If point p lies above line L, then line D(p) lies below point D(L); and symmetrically if p lies below L, D(p) lies above D(L).

Duality is very important in computational geometry since it allows us to map certain problems to equivalent, but more understandable problems.  See [1] for many interesting examples of duality.

Usage
The usage of Dual is very straightforward.  There are three windows: a Primal Plane window, which shows lines and points in the dual plane; a Dual Plane window, which shows the transformed lines and points (from the primal plane); and a Primal Data window, which shows the primal points and lines in a non-graphical format.
	To enter a point into the primal or dual plane, first select the Points radio button in the Primal Data window.  Then click left mouse button in the primal or dual plane window where you want to enter a point.  
	To enter a line into the primal or dual plane, first select the Lines radio button in the Primal Data window.  Then click left mouse button in the primal or dual plane window at the first endpoint of the line, and then click again for the second endpoint of the line.  
	Each point and line has an associated label and color that you specify.  When a new point or line is entered, an increasing integer is automatically used as the label.  Also, the color used is the current color in the point or line color well.  To change a label, select the point or line to change in the browser and edit the label in the text field below the browser.  To change a color, select the point or line to change in the browser, click on the edge of the color well to bring up the color wheel, and specify a new color.

Comments
If you found this program useful, or would like to extend it in any way, please let me know.

References
1. Computational Geometry in C, Joseph O'Rourke.